import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-04-17
 * Time: 17:25
 */

public class Solution {


    /**
     * 时间复杂度为 n^3
     * @param s string字符串
     * @return int整型
     */
    public int minCut (String s) {
        int len = s.length();
        int[] min = new int[len+1];
        Arrays.fill(min, len-1);
        for (int i = 1; i <= len; i++) {
            // 如果这个子串本身就是一个回文串, 那么就不用分割
            if(isReverse(s.substring(0, i))){
                min[i] = 0;
                continue;
            }
            for (int j = 1; j < i ; j++) {
                if(isReverse(s.substring(j ,i))){
                    // 注意这里面要找的分割次数最少的
                    min[i] = Math.min(min[j] + 1, min[i]);
                }
            }
        }
        return min[len];
    }

    /**
     * 判断一个字符串是不是一个回文串
     * @param s
     * @return
     */
    public boolean isReverse(String s){
        int len = s.length();
        int begin = 0;
        int end = len - 1;
        while (begin < end){
            if(s.charAt(begin) != s.charAt(end)){
                return false;
            }
            begin++;
            end--;
        }
        return true;
    }

    /**
     * 使用 DP 提前将 [i, j] 是回文子串的标记好
     * 这样时间复杂度降到 n^2
     */
    public static boolean[][] mat;
    public static void getMat(String s){
        int len = s.length();
        mat = new boolean[len+1][len+1];
        mat[0][0] = true;
        for (int i = len; i > 0 ; i--) {
            for (int j = i; j <= len ; j++) {
                if(i == j){
                    mat[i][j] = true;
                    continue;
                }
                if(s.charAt(i-1) == s.charAt(j-1)){
                    if(j == i+1 || mat[i+1][j-1]){
                        mat[i][j] = true;
                    }
                }
            }
        }
    }

    public static int minCut2(String s) {
        getMat(s);
        int len = s.length();
        int[] min = new int[len+1];
        // 注意先初始化为最大值
        Arrays.fill(min, len-1);
        for (int i = 1; i <= len; i++) {
            // 如果这个子串本身就是一个回文串, 那么就不用分割
            if(mat[1][i]){
                min[i] = 0;
                continue;
            }
            for (int j = 1; j <= i ; j++) {
                if(mat[j][i]){
                    // 注意这里面要找的分割次数最少的
                    min[i] = Math.min(min[j-1] + 1, min[i]);
                }
            }
        }
        return min[len];
    }
}
